﻿<h1>边界检查消除</h1>

<p>
Go是一个内存安全的语言。在数组和切片的索引和子切片操作中，Go运行时将检查操作中使用的下标是否越界。
如果下标越界，一个恐慌将产生，以防止这样的操作破坏内存安全。这样的检查称为边界检查。
边界检查使得我们的代码能够安全地运行；但是另一方面，也使得我们的代码运行效率略微降低。
</p>

<p>
从Go官方工具链1.7开始，官方标准编译器使用了一个新的基于SSA（single-assignment form，静态单赋值形式）的后端。
SSA使得Go编译器可以有效利用诸如<a href="https://en.wikipedia.org/wiki/Bounds-checking_elimination">BCE</a>（bounds check elimination，边界检查消除）和<a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination">CSE</a>（common subexpression elimination，公共子表达式消除）等优化。
BCE可以避免很多不必要的边界检查，CSE可以避免很多重复表达式的计算，从而使得编译器编译出的程序执行效率更高。有时候这些优化的效果非常明显。
</p>

<p>
本文将展示一些例子来解释边界检查消除在官方标准编译器1.7+中的表现。
</p>

<p>
对于Go官方工具链1.7+，我们可以运行<code>go build <b>-gcflags="-d=ssa/check_bce/debug=1"</b></code>来列出哪些代码行仍然需要边界检查。
</p>

<h3>例子1</h3>

<div>
<pre class="line-numbers must-line-numbers"><code class="language-go">// example1.go
package main

func f1(s []int) {
	_ = s[0] // 第5行： 需要边界检查
	_ = s[1] // 第6行： 需要边界检查
	_ = s[2] // 第7行： 需要边界检查
}

func f2(s []int) {
	_ = s[2] // 第11行： 需要边界检查
	_ = s[1] // 第12行： 边界检查消除了！
	_ = s[0] // 第13行： 边界检查消除了！
}

func f3(s []int, index int) {
	_ = s[index] // 第17行： 需要边界检查
	_ = s[index] // 第18行： 边界检查消除了！
}

func f4(a [5]int) {
	_ = a[4] // 第22行： 边界检查消除了！
}

func main() {}
</code></pre>

<pre class="output"><code>$ go build -gcflags="-d=ssa/check_bce/debug=1" example1.go
./example1.go:5: Found IsInBounds
./example1.go:6: Found IsInBounds
./example1.go:7: Found IsInBounds
./example1.go:11: Found IsInBounds
./example1.go:17: Found IsInBounds
</code></pre>

<p>
我们可以看到函数<code>f2</code>中的第<i>12</i>行和第<i>13</i>行不再需要边界检查了，因为第<i>11</i>行的检查确保了第<i>12</i>行和第<i>13</i>行中使用的下标肯定不会越界。
</p>

<p>
但是，函数<code>f1</code>中的三行仍然都需要边界检查，因为第<i>5</i>行中的边界检查不能保证第<i>6</i>行和第<i>7</i>行中的下标没有越界，第<i>6</i>行中的边界检查也不能保证第第<i>7</i>行中的下标没有越界。
</p>

<p>
在函数<code>f3</code>中，编译器知道如果第一个<code>s[index]</code>是安全的，则第二个<code>s[index]</code>是无需边界检查的。
</p>

<p>
编译器也正确地认为函数<code>f4</code>中的唯一一行（第<i>22</i>行）是无需边界检查的。
</p>
</div>

<h3>例子2</h3>

<div>
<pre class="line-numbers must-line-numbers"><code class="language-go">// example2.go
package main

func f5(s []int) {
	for i := range s {
		_ = s[i]
		_ = s[i:len(s)]
		_ = s[:i+1]
	}
}

func f6(s []int) {
	for i := 0; i < len(s); i++ {
		_ = s[i]
		_ = s[i:len(s)]
		_ = s[:i+1]
	}
}

func f7(s []int) {
	for i := len(s) - 1; i >= 0; i-- {
		_ = s[i]
		_ = s[i:len(s)]
	}
}

func f8(s []int, index int) {
	if index >= 0 && index < len(s) {
		_ = s[index]
		_ = s[index:len(s)]
	}
}

func f9(s []int) {
	if len(s) > 2 {
	    _, _, _ = s[0], s[1], s[2]
	}
}

func main() {}
</code></pre>

<pre class="output"><code>$ go build -gcflags="-d=ssa/check_bce/debug=1" example2.go
</code></pre>

<p>
酷！官方标准编译器消除了上例程序中的所有边界检查。
</p>

<p>
注意：在Go官方工具链1.11之前，官方标准编译器没有足够聪明到认为第<i>22</i>行是不需要边界检查的。
</p>

</div>

<h3>例子3</h3>

<div>
<pre class="line-numbers must-line-numbers"><code class="language-go">// example3.go
package main

import "math/rand"

func fa() {
	s := []int{0, 1, 2, 3, 4, 5, 6}
	index := rand.Intn(7)
	_ = s[:index] // 第9行： 需要边界检查
	_ = s[index:] // 第10行： 边界检查消除了！
}

func fb(s []int, index int) {
	_ = s[:index] // 第14行： 需要边界检查
	_ = s[index:] // 第15行： 需要边界检查（不够智能？）
}

func fc() {
	s := []int{0, 1, 2, 3, 4, 5, 6}
	s = s[:4]
	index := rand.Intn(7)
	_ = s[:index] // 第22行： 需要边界检查
	_ = s[index:] // 第23行： 需要边界检查（不够智能？）
}

func main() {}
</code></pre>

<pre class="output"><code>$ go build -gcflags="-d=ssa/check_bce/debug=1" example3.go
./example3.go:9: Found IsSliceInBounds
./example3.go:14: Found IsSliceInBounds
./example3.go:15: Found IsSliceInBounds
./example3.go:22: Found IsSliceInBounds
./example3.go:23: Found IsSliceInBounds
</code></pre>

<p>
噢，仍然有这么多的边界检查！
</p>

<p>
但是等等，为什么官方标准编译器认为第<i>10</i>行不需要边界检查，却认为第<i>15</i>和第<i>23</i>行仍旧需要边界检查呢？
是标准编译器不够智能吗？
</p>

<p>
事实上，这里标准编译器做得对！为什么呢？
原因是一个子切片表达式中的起始下标可能会大于基础切片的长度。
让我们先看一个简单的使用了子切片的例子：
</p>

<pre class="line-numbers must-line-numbers"><code class="language-go">package main

func main() {
	s0 := make([]int, 5, 10)
	// len(s0) == 5, cap(s0) == 10

	index := 8

	// 在Go中，对于一个子切片表达式s[a:b]，a和b须满足
	// 0 <= a <= b <= cap(s);否则，将产生一个恐慌。

	_ = s0[:index]
	// 上一行是安全的不能保证下一行是无需边界检查的。
	// 事实上，下一行将产生一个恐慌，因为起始下标
	// index大于终止下标（即切片s0的长度）。
	_ = s0[index:] // panic
}
</code></pre>

<p>
所以<b>如果<code>s[:index]</code>是安全的则<code>s[index:]</code>是无需边界检查的</b>这条论述只有在<code>len(s)</code>和<code>cap(s)</code>相等的情况下才正确。这就是函数<code>fb</code>和<code>fc</code>中的代码仍旧需要边界检查的原因。
</p>

<p>
标准编译器成功地检测到在函数<code>fa</code>中<code>len(s)</code>和<code>cap(s)</code>是相等的。干得漂亮！Go语言开发团队！
</p>

</div>

<h3>例子4</h3>

<div>
<pre class="line-numbers must-line-numbers"><code class="language-go">// example4.go
package main

import "math/rand"

func fb2(s []int, index int) {
	_ = s[index:] // 第7行： 需要边界检查
	_ = s[:index] // 第8行： 边界检查消除了！
}

func fc2() {
	s := []int{0, 1, 2, 3, 4, 5, 6}
	s = s[:4]
	index := rand.Intn(7)
	_ = s[index:] // 第15行： 需要边界检查
	_ = s[:index] // 第16行： 边界检查消除了！
}

func main() {}
</code></pre>

<pre class="output"><code>$ go build -gcflags="-d=ssa/check_bce/debug=1" example4.go
./example4.go:7:7: Found IsSliceInBounds
./example4.go:15:7: Found IsSliceInBounds
</code></pre>

在此例子中，标准编译器成功推断出：
<ul>
<li>
	在函数<code>fb2</code>中，如果第<i>7</i>行是安全的，则第<i>8</i>行是无需边界检查的；
</li>
<li>
	在函数<code>fc2</code>中，如果第<i>15</i>行是安全的，则第<i>16</i>行是无需边界检查的。
</li>
</ul>

<p>
注意：Go官方工具链1.9之前中的标准编译器没有出推断出第<i>8</i>行不需要边界检查。
</p>

</div>

<h3>例子5</h3>

<div>
当前版本的标准编译器并非足够智能到可以消除到一切应该消除的边界检查。
有时候，我们需要给标准编译器一些暗示来帮助标准编译器将这些不必要的边界检查消除掉。

<pre class="line-numbers must-line-numbers"><code class="language-go">// example5.go
package main

func fd(is []int, bs []byte) {
	if len(is) >= 256 {
		for _, n := range bs {
			_ = is[n] // 第7行： 需要边界检查
		}
	}
}

func fd2(is []int, bs []byte) {
	if len(is) >= 256 {
		is = is[:256] // 第14行： 一个暗示
		for _, n := range bs {
			_ = is[n] // 第16行： 边界检查消除了！
		}
	}
}

func fe(isa []int, isb []int) {
	if len(isa) > 0xFFF {
		for _, n := range isb {
			_ = isa[n & 0xFFF] // 第24行： 需要边界检查
		}
	}
}

func fe2(isa []int, isb []int) {
	if len(isa) > 0xFFF {
		isa = isa[:0xFFF+1] // 第31行： 一个暗示
		for _, n := range isb {
			_ = isa[n & 0xFFF] // 第33行： 边界检查消除了！
		}
	}
}

func main() {}
</code></pre>

<!--
since Go官方工具链1.11, the compiler becomes more smarter

func ff(s []int) []int {
	s2 := make([]int, len(s))
	for i := range s {
		s2[i] = -s[i] // 第41行： bounds check, not smart enough
	}
	return s2
}

func ff2(s []int) []int {
	s2 := make([]int, len(s))
	s2 = s2[:len(s)] // 第48行： to avoid bounds check at 第50行
	for i := range s {
		s2[i] = -s[i] // 第50行： bounds check eliminated!
	}
	return s2
}
-->

<pre class="output"><code>$ go build -gcflags="-d=ssa/check_bce/debug=1" example5.go
./example5.go:7: Found IsInBounds
./example5.go:24: Found IsInBounds
</code></pre>
</div>

<h3>总结</h3>

<p>
本文上面列出的例子并没有涵盖标准编译器支持的所有边界检查消除的情形。本文列出的仅仅是一些常见的情形。
</p>

<p>
尽管标准编译器中的边界检查消除特性依然不是100%完美，但是对很多常见的情形，它确实很有效。
自从标准编译器支持此特性以来，在每个版本更新中，此特性都在不断地改进增强。
无需质疑，在以后的版本中，标准编译器会更加得智能，以至于上面第5个例子中提供给编译器的暗示有可能将变得不再必要。
谢谢Go语言开发团队出色的工作！
</p>

<h3>参考：</h3>
<div>
<ol>
<li><a href="https://docs.google.com/document/d/1vdAEAjYdzjnPA9WDOQ1e4e05cYVMpqSxJYZT33Cqw2g">Bounds Check Elimination</a></li>
<li>
	<a href="https://talks.godoc.org/github.com/klauspost/talks/2016/go17-compiler.slide">Utilizing the Go 1.7 SSA Compiler</a>（<a href="https://talks.godoc.org/github.com/klauspost/talks/2016/go17-compiler-2.slide">第二部分</a>）
</li>
</ol>
</div>
